package lc;

import lc.q51_100.Q52;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
 *
 */
public class Q523 {

    public boolean checkSubarraySum2(int[] nums, int k) {
        if (k < 0) {
            k = -k;
        }
        Map<Integer, Integer> index = new HashMap<>();
        index.put(0, -1);
        int sum = 0;
        if (k == 0) {
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (index.containsKey(sum)) {
                    final Integer h = index.get(sum);
                    if (i - h > 1) {
                        return true;
                    }
                } else {
                    index.put(sum, i);// 放第一次即可
                }
            }
        } else {
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                int y = sum % k;
                if (index.containsKey(y)) {
                    final Integer h = index.get(y);
                    if (i - h > 1) {
                        return true;
                    }
                } else {
                    index.put(y, i);// 放第一次即可
                }
            }
        }
        return false;

    }

    public boolean checkSubarraySum(int[] nums, int k) {
        // 先暴力求解
        int[] nums2 = new int[nums.length + 1];
        nums2[0] = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            nums2[i + 1] = sum;
        }
        for (int i = 0; i < nums2.length - 2; i++) {
            for (int j = i+2; j < nums2.length; j++) {
                final int l = nums2[j] - nums2[i];
                if (k == 0 && l == 0) {
                    return true;
                } else if (k != 0 && l % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        final Q523 q523 = new Q523();
        System.out.println(q523.checkSubarraySum(new int[]{0,1,0}, 0));
    }
}
